#ifndef __BIN_H__
#define __BIN_H__

#include "cpp_framework.h"

using namespace CMDR;

template<class T, T _NULL_VALUE>
class Bin {
private:
	class Node : public HazardMemory::Object {
	public:
		const T					_value;
		VolatileType<Node*>	_next;
		
		Node(T item) : _next(NULL), _value(item) {}
		~Node() {}

		virtual bool isValid() {
			return true;
		}

		virtual HazardMemory::Object* getNextValid(const int indx) {
			return _next;
		}

		virtual HazardMemory::Object* getNextValid(const int indx, int& stamp) {
			stamp = 0;
			return _next;
		}
	};

	AtomicReference<Node>  _head;

public:
	Bin() { }
	~Bin() {
		clear();
	}
  	
	void put(T item) {
		Node * newHead = new Node(item);
		while(true) {
			newHead->_next = _head.get();
			if (_head.compareAndSet(newHead->_next, newHead))
				return;
		} 
	}
  	
	T get() {
		HazardMemory::Ptr<Node> pHead;
		HazardMemory::Ptr<Node> pNext;

		while(true) {
			pHead = _head;

			if(null == pHead.getReference())
				return _NULL_VALUE;

			pNext.extractNext(pHead,0);

			if(_head.compareAndSet(pHead.getReference(), pNext.getReference())) {
				const T return_value = pHead->_value;
				pHead.retire();			
				return return_value;
			}
		}
	}
    
	T peek() {
		HazardMemory::Ptr<Node> pHead;
		pHead = _head;
		if(null == pHead.getReference())
			return _NULL_VALUE;
		return pHead->_value;
	}
  	
	bool isEmpty() {
		return (null == (_head.get()));
	}

	void clear() {
		Node* temp,*next;
		temp = _head.get();
		while (null != temp) {
			next=temp->_next;
			delete temp;
			temp=next;
		}
	}

	int size() {
		Node* temp = _head.get();
		if (null == temp || _NULL_VALUE == temp->_value) 
			return 0;

		int result=1;
		while(null != (temp=temp->_next)) {
			if(_NULL_VALUE != temp->_value) 
				++result;
		}
		return result;
	}
};

#endif
